class Solution {
    vector<vector<string>> ans;
    void backTracking(vector<vector<char>> &chessboard, int n, int row)
    {
        if(n == row)
        {
            // 收获结果，走到这，一定是合法的N皇后棋盘
            vector<string> tmp;
            for(int i = 0; i < n; i++)
            {
                string str;
                for(int j = 0; j < n; j++)
                    str += chessboard[i][j];
                tmp.push_back(str);
            }
            ans.push_back(tmp);
            return;
        }

        for(int i = 0; i < n; i++)
        {
            if(isValid(chessboard, row, i, n))    // isValid的作用是我这个位置如果放了皇后是合法的，此时还没放呢！先假设放了
            {
                chessboard[row][i] = 'Q';
                backTracking(chessboard, n, row + 1);
                chessboard[row][i] = '.';         // 回溯的关键步骤
            }

            // 如果棋盘不合法，那么自然不会添加，那么就会返回
        }
    }

    bool isValid(vector<vector<char>> &chessboard, int row, int col, int n)
    {
        // 判断行
        for(int i = row, j = 0; j < n; j++)
            if(chessboard[i][j] == 'Q' && j != col) return false;

        // 判断列
        for(int i = 0, j = col; i < n; i++)
            if(chessboard[i][j] == 'Q' && i != row) return false;

        // 判断右上
        for(int i = row, j = col; i >= 0 && j < n; i--, j++)
            if(chessboard[i][j] == 'Q') return false;

        // 判断左上
        for(int i = row, j = col; i >= 0 && j >= 0; i--, j--)
            if(chessboard[i][j] == 'Q') return false;
        return true;
    }

public:
    vector<vector<string>> solveNQueens(int n) {
        // 定义棋盘并初始化为'.'
        vector<vector<char>> chessboard(n, vector<char>(n, '.'));
        // 调用回溯函数
        backTracking(chessboard, n, 0);
        return ans;
    }
};